Reverse Linked List II

LeetCode 92 | Difficulty: Medium

Medium

Problem Description

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:

- The number of nodes in the list is `n`.

- `1 <= n <= 500`

- `-500 <= Node.val <= 500`

- `1 <= left <= right <= n`

Follow up: Could you do it in one pass?

Topics: Linked List

---

Approach

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 165 ms)

Metric	Value
Runtime	165 ms
Memory	N/A
Date	2017-09-22

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode ReverseBetween(ListNode head, int m, int n) {
        if (head == null || head.next == null) return head;
        
        ListNode dummy = new ListNode(Int32.MinValue);
        dummy.next = head;
        ListNode front = dummy;
        ListNode temp = dummy;
        for (int i = 0; i < m-1; i++)
        {
            temp = temp.next;           
        }
        front = temp;
        ListNode oldHead = front.next;
        for (int i = m; i < n+1; i++)
        {
            temp=temp.next;
        }
        ListNode oldTail = temp;
        ListNode rear = temp.next;      
        oldTail.next = null;
        front.next = Reverse(oldHead);
        oldHead.next = rear;
        return dummy.next;
    }
    
    private static ListNode Reverse(ListNode head)
    {
        ListNode rev = null;
        while (head != null)
        {
            ListNode temp = head;
            head = head.next;
            temp.next = rev;
            rev = temp;
        }
        return rev;
    }
}

---

Complexity Analysis

Approach	Time	Space
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.